#pragma once
#include <vector>
#include <algorithm>
using namespace std;
/*
* 使用动态规划, 解决背包问题
*/

typedef struct Stuff {
	int Weight;
	int Value;
};

int DynamicProgramming(const vector<Stuff>& stuffs, int total) {
	/*
	* 现在使用一个表格,：
	* 1.行代表背包装多少物品(表示能装到物品的编号)
	* 2.列表示背包的容量
	* 
	* 那么每个格子表示在当前背包的容量下, 考虑前 n 个物品的能装入的最大价值
	* 所以在最右下角, 为总容量和总物品选取的最大价值(最优解)
	* 第一行和第一列为 0, 前 0 个 / 容量为 0, 最大价值为 0
	* 
	* |       \ 背包容量| 0 1 2 3 4 ..... total
	* |物品编号 \	   |
	* | 0			   | 0 0 0 0 0 ...... 0
	* | 1              | 0
	* | 2              | 0
	* |...             | .
	* |stuffs.size()   | 0
	* 
	* 从左上角 (1, 1) 开始填表
	* 首先判断 1 号物品能否放入背包, 若不能则和 (0, 1) 相同
	* 若能够装下:
	*	1.不装当前物品, 和 (0, 1) 相同
	*	2.装入物品, 剩余容量 = 当前的容量 - 物品容量
	*	  然后考虑剩余容量下其他物品的最佳选择, 例如:
	*	      若当前格子为 (3, 4), 3 号 物品重量为 2, 则需要去寻找 (2, 2) 格子,
	*         然后用 (2, 2) + 3 号物品价值 与 (2, 4) 进行比较,
	*         即比较 放入物品后 与 不放入物品 的价值, 使用价值高的作为结果。
	*/

	//初始化表格
	vector<vector<int>> dynamicProgram(stuffs.size() + 1, vector<int>(total + 1, 0));
	
	for (int row = 1; row <= stuffs.size(); row++) {
		for (int col = 1; col <= total; col++) {
			//能装下
			if (stuffs[row - 1].Weight <= col) {
				//比较装 与 不装 的价值
				dynamicProgram[row][col] =
					max(dynamicProgram[row - 1][col - stuffs[row - 1].Weight] + stuffs[row - 1].Value,
						dynamicProgram[row - 1][col]);
			}

			//不能装下, 则为前 n - 1 最大价值
			else
				dynamicProgram[row][col] = dynamicProgram[row - 1][col];
		}
	}
	
	return dynamicProgram[stuffs.size()][total];
}